Gate arrays are well-known in the art. These are semiconductor integrated devices which are customizable by the user to form a plurality of customized electrical circuits. Each electrical circuit is a logic unit or a macro, such as a logic gate, (AND, NAND, OR, NOR, etc.) or a more complex logic unit such as latch, flip-flop, adder, etc. The gate arrays are customized both to form the logic units and to interconnect the logic units. Hereinafter, the customized connection to form a logic unit will be referred to as the intra logic unit connection. The customized connection between the logic units will be referred to as the inter logic unit connection.
Typically, a gate array is comprised of a base array which has a plurality of transistors of the P conductivity type and of the N conductivity type arranged in an orderly array. The base array is then customized to provide the intra logic unit and inter logic unit connections. The customized circuits are formed by providing the electrical connection (typically, the metal mask layer(s)) to interconnect the transistors. Thus, a gate array is comprised of a base array which is common for all users and one or more metal interconnection layers which customizes the semiconductor device for the particular user's electrical circuit requirements.
In the prior art, gate arrays are formed by forming a base array of P type and N type transistors in a substrate. In an article entitled "Advanced CMOS Gate Array Architecture Combining `Gate Isolation` And Programmable Routing Channels" by Wilhelmus Van Noije and Gilbert Declerck, published in the IEEE Journal Of Solid State Circuits, Vol. SC-20, No. 2, Apr. 1985, the authors described a gate array comprising a plurality of drain-source diffusion regions that are positioned in a substrate arranged in an array. The drain-source diffusion regions are spaced apart from one another. A plurality of gate regions are positioned on the substrate and are spaced apart from one another with each gate region lying substantially between a pair of adjacent drain-source diffusion regions. Thus, a chain of continuously electrically connected transistors is formed with the drain of each transistor electrically connected to the source of an adjacent transistor. The terms "drain" and "source" may be used interchangeably. Logic units are formed in such a chain of electrically connected transistors with an isolation transistor provided between each logical unit. The gate of the isolation transistor is connected to a voltage source, thereby isolating the logical units. If the isolation transistor is P conductivity type, the gate of the isolation transistor is connected to V.sub.dd. If the isolation transistor is N conductivity type, the gate of the isolation transistor is connected to ground.
In the prior art, the interconnection of the transistors in a gate array to form the intra logic unit connection has been done by manual methods. Customizable gate arrays are typically referred to as semi-custom circuits, because the layout of the transistors in the gate array, i.e. the base array, has been pre-arranged.
A completely customized circuit is one in which none of the circuit element's layout has been prearranged. Thus, the circuit designer has total freedom in the layout of the circuit elements. One technique to layout a completely customized circuit is disclosed in a paper entitled "Automated Design Of CMOS Leaf Cells" by John T. Nogatch and Tom Hedges, published in the November 1985 issue of VLSI Systems Design, page 66. That technique is based upon the principle of the formation of a single diffusion line which connects a drain of a transistor to a source of a transistor through all the transistors.
The use of cost functions for transistor placement optimization is well known in the art. Cost functions are equations that are used to determine the efficiency of a particular layout of semiconductor circuits.